#include <set>
#include <vector>
using namespace std;

class Solution
{
public:
    bool containsNearbyAlmostDuplicate(vector<int> &nums, int k, int t)
    {
        if (k >= nums.size())
            k = nums.size() - 1;
        // 保持滑动窗口有序
        // 每次插入删除 logn 比每次构建数组+排序好
        set<long> rb_tree;
        for (int i = 0; i < nums.size(); i++)
        {
            // 有序 支持二分查找 采用区间法 只要x在[nums[i]-t,nums[i]-+t] 即可
            auto it = rb_tree.lower_bound((long)nums[i] - t);
            if (it != rb_tree.end() && *it <= (long)nums[i] + t)
            {
                return true;
            }
            rb_tree.insert(nums[i]);
            if (i > k - 1)
            {
                rb_tree.erase(nums[i - k]);
            }
        }
        return false;
    }
};